package LearnDataStructure.c_树结构.有序树.二叉树.红黑树;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;

import java.util.List;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-10 14:57
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.有序树.二叉树.平衡二叉树.红黑树
 */
/**
 * 红黑树
 * 1)每个节点要么是红色要么是黑色
 * 2)根节点是黑色的
 * 3)每个叶子节点(NIL)是黑色
 * 4)红色节点的的子节点都是黑色的
 * 5)对每个节点，从该节点到其后代叶子节点的简单路径上，均包含数目相同的黑色节点
 * 通常我们认为树末梢的节点还有两个为空的节点，这些空节点是黑色的，所以不必检测第三条
 */
public class d_MyRBTree<K, V> extends b_MyBinaryTreebyLinked<K,V> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    /**
     * 这个插入既满足平衡又满足染色正确
     * @param key
     * @param value
     * @return
     */
    @Override
    public BSTNode<K, V> insert(K key, V value) {
        BSTNode<K, V> newNode = super.insert(key,value);
        BSTNode<K, V> parent = newNode.parent;
        //对插入newNode后的新树进行重新染色
        rePaint(parent,newNode);
        //对根节点染黑
        colorBlack(getRoot());
        return newNode;
    }

    /**
     * 对添加节点后的新树进行重新染色
     * @param parent
     * @param newNode
     */
    private void rePaint(BSTNode<K, V> parent, BSTNode<K, V> newNode) {
        if (parent == null) {
            setRoot(newNode);
            return;
        }
        //$$$如果newNode的父节点parent是红色，需要进行操作
        if (colorOf(parent) == RED) {
            BSTNode<K, V> grand = parent.parent;//进了这个判断，parent必定有parent；而且grand一定是黑色，由“红不连”这个规则得出
            BSTNode<K, V> uncle = parent.isLeftChild ? grand.right : grand.left;
            //***如果uncle存在，同时uncle是红色，则进行操作
            if (uncle != null && colorOf(uncle) == RED) {
                BSTNode<K, V> p = grand;
                BSTNode<K, V> q = parent;
                BSTNode<K, V> s = newNode;
                //反转父子节点的颜色；此时以p为根节点的子树符合红黑树规则
                colorRed(p);
                colorBlack(q);
                colorBlack(uncle);
                //顺着树向上递归操作；因为p以上的节点的子树不一定符合红黑树规则
                rePaint(p.parent, p);
            } else {//***如果uncle不存在，或者uncle是黑色，则进行另一些操作
                /*
                四种类型分开讨论
                如果你想问为什么uncle不存在，或者uncle是黑色时，我们不需要递归？
                你可以去画图，
                因为此情况下，我们“旋转”、“重染色”后，得到的新子树，其根节点的颜色，与“旋转”、“重染色”前的旧子树的根节点颜色是一样的
                所以没有破坏原整棵树的颜色
                所以不用递归
                 */
                BSTNode<K, V> p = grand;
                BSTNode<K, V> q = parent;
                BSTNode<K, V> s = newNode;

                if (q.isLeftChild && s.isLeftChild) {//左左型
                    //反转父子节点的颜色
                    colorRed(p);
                    colorBlack(q);

                    rightRotate(p,q);
                } else if (!q.isLeftChild && !s.isLeftChild) {//右右型
                    //反转父子节点的颜色
                    colorRed(p);
                    colorBlack(q);

                    leftRotate(p,q);
                } else if (q.isLeftChild && !s.isLeftChild) {//左右型
                    leftRotate(q,s);//先左旋，成为左左型
                    //反转父子节点的颜色
                    colorRed(p);
                    colorBlack(s);

                    rightRotate(p,s);
                } else {//右左型
                    rightRotate(q,s);
                    //反转父子节点的颜色
                    colorRed(p);
                    colorBlack(s);

                    leftRotate(p,s);
                }
            }
        }
        //$$$否则，parent是黑色，则不进行任何操作,因为没有破坏红黑树规则;而且如果parent是root，因为root永远是黑色，所以也不进行操作
    }

    private boolean colorOf(BSTNode<K, V> node) {
        if (node == null) {
            return false;
        }
        return node.isRed;
    }

    private void colorBlack(BSTNode<K,V> node) {
        if (node != null) {
            node.isRed = false;
        }
    }

    private void colorRed(BSTNode<K, V> node) {
        if (node != null) {
            node.isRed = true;
        }
    }

    /**
     * 红黑树删除及修复
     1、双支转单支
     2、删除D，并顶替N
     3、D为黑，需修复
     4  N为红，很简单（N变黑即可）
        N为黑，系列复杂的修复
     * @param key
     */
    @Override
    public void remove(K key) {
        BSTNode<K, V> toDelete = getValue(key);
        if (toDelete == null) {//错误情况，要删除节点找不到
            return;//不删了直接返回
        }
        /*
        准备阶段
        如果toDelete是严格的内部节点，
        拷贝后继元素的内容到toDelete，
        然后toDelete指向后继，
        这个准备阶段如果需要用到，会在后面用；当然这个准备阶段也有可能不会执行，例如toDelete是叶子节点
         */
        if (toDelete.left != null && toDelete.right != null) {//只有“拥有双子”，才能成为严格的内部节点
            K successorKey = successor(toDelete.key);
            BSTNode<K, V> successorNode = getValue(successorKey);
            toDelete.key = successorKey;//交换key
            toDelete.value = successorNode.value;
            toDelete = successorNode;//指针指向后继successorNode
            /*
            如果确实执行了“准备阶段”的代码
            那么后续庞杂的if判断中的，实际要删除的节点，就是successorNode
            在指针角度看，toDelete就指的是successorNode
            不要迷糊了哦
             */
        }
        /*
        庞杂的if判断阶段
        此时，toDelete(指向的是successorNode)一定是单支，或者是叶子
        那么，用于顶替这个实际要删除的“节点toDelete”,我们就设为N
        N有可能为null，当toDelete是叶子节点的时候！
         */
        BSTNode<K, V> N = toDelete.left != null ? toDelete.left : toDelete.right;
        //庞杂if判断开始
        if (N == null && toDelete.parent == null) {     //case1-a:toDelete==root, 把树删空
            /*
            因为我们要删除toDelete，而且N顶替节点为null
            也就是说，整棵树就一个节点root
            那么直接删呗
            */
            setRoot(null);
        } else if (N != null) {//TODO 注意啊这里的判断是先删后修！！！
            //可以顶替；开始顶替操作---------------------------------------
            N.parent = toDelete.parent;
            if (toDelete.parent == null) {              //case1-b:toDelete==root , N != null, N成为新根节点
                setRoot(N);
                colorBlack(N);//顺便直接染色
            } else if (toDelete.isLeftChild) {          //case2-a:toDelete!=root ,toDelete 是 left 和 RED, N != null ,N成为新left
                toDelete.parent.left = N;
                N.isLeftChild = true;
            } else {                                    //case2-b:toDelete!=root ,toDelete 是 right 和 RED, N != null ,N成为新right
                toDelete.parent.right = N;
                N.isLeftChild = false;
            }
            //删除toDelete
            toDelete.parent = null;
            toDelete.left = null;
            toDelete.right = null;
            //结束顶替操作-----------------------------------------------

            //因为已经执行了删除；判断是否需要修复整棵树;此判断包含下面2种情况;
            if (colorOf(toDelete) == BLACK) {           //case3-a:toDelete!=root ,toDelete 是 left 和 BLACK, N != null ,N成为新left
                                                        //case3-b:toDelete!=root ,toDelete 是 right 和 BLACK, N != null ,N成为新right
                fixAfterDeletion(N);
            }
        } else {//(N == null && toDelete.parent != null)
            if (colorOf(toDelete) == BLACK) {
                fixAfterDeletion(toDelete);//TODO 先修复整棵树颜色，再删除！
                if (toDelete.isLeftChild) {             //case4-a:toDelete!=root ,toDelete 是 left 和 BLACK 和 叶子节点, N == null
                    toDelete.parent.left = null;
                } else {                                //case4-b:toDelete!=root ,toDelete 是 right 和 BLACK 和 叶子节点, N == null
                    toDelete.parent.right = null;
                }
                toDelete.parent = null;
            } else {
                if (toDelete.isLeftChild) {             //case5-a:toDelete!=root ,toDelete 是 left 和 RED 和 叶子节点, N == null
                    toDelete.parent.left = null;
                } else {                                //case5-b:toDelete!=root ,toDelete 是 right 和 RED 和 叶子节点, N == null
                    toDelete.parent.right = null;
                }
                toDelete.parent = null;
            }
        }
        size--;
    }

    /**
     * 修复整棵树的颜色
     * 不算case0，就有6种情况！
     * @param N
     */
    private void fixAfterDeletion(BSTNode<K,V> N) {
        //简单情况;就一种
        if (colorOf(N) == RED) {            //case0: toDelete == BLACK, N == RED
            colorBlack(N);
        //复杂情况
        } else if (N.parent == null){       //case1: toDelete == BLACK, N == BLACK, N != null, N.parent == null, 实际上就是case1-b
                                            //所以空判断体，不做任何操作；因为case1-b用不上fixAfterDeletion.因为此时N == root
        } else {                            //case2: toDelete == BLACK, N == BLACK, N != null, N.parent != null, 实际上就是case3-a case3-b
            useCase2(N);
        }
    }

    /**
     * case2:从当前的N视角看 brother == RED, N == BLACK
     * 执行的手段是：make brother == BLACK, parent(toDelete.parent) == RED, 然后左旋或者右旋
     * 结果是将case2转变为case3
     * 结果状态是，如果N(BLACK)是left, brother(BLACK)的left是parent, parent(RED)的left是N
     * @param N
     */
    private void useCase2(BSTNode<K, V> N) {
        BSTNode<K, V> parent = N.parent;
        BSTNode<K, V> brother = getBrother(N, parent);
        if (colorOf(brother) == RED) {
            colorBlack(brother);
            colorRed(parent);
            if (N.isLeftChild) {
                leftRotate(parent,brother);
                // leftRotate(parent,N);
            } else {
                rightRotate(parent,brother);
                // rightRotate(parent,N);
            }
        }
        useCase3(N);
    }

    private BSTNode<K, V> getBrother(BSTNode<K, V> N, BSTNode<K, V> parent) {
        BSTNode<K, V> brother = null;
        if (N.isLeftChild) {
            brother = parent.right;
        } else {
            brother = parent.left;
        }
        return brother;
    }

    /**
     * case3:从当前的N视角看 brother == BLACK, N == BLACK
     * brother是case2中的brother的left
     *
     * 如果是从case2进入的case3，则：
     * 从当前的N视角看 brother == BLACK, N == BLACK, parent == RED
     * brother是case2中的brother的left
     * parent任然是case2中的parent
     *
     * 执行的手段是：如果brother双子黑且parent == BLACK, make brother == RED, 然后向上递归检查整棵树颜色是否安全
     * 结果状态是，如果N(BLACK)是left, brother(RED)的(如果brother两孩子存在的话)left和right都是BLACK, parent(BLACK)的left是N
     *
     * 如果是从case2进入的case3，则执行的手段是：
     * 将case3转变为case4
     * 结果状态是，如果N(BLACK)是left, brother(BLACK), parent(RED)的left是N
     * @param N
     */
    private void useCase3(BSTNode<K, V> N) {
        BSTNode<K, V> parent = N.parent;
        BSTNode<K, V> brother = getBrother(N, parent);
        if (
                colorOf(parent) == BLACK &&
                (brother.left == null || colorOf(brother.left) == BLACK) &&
                (brother.right == null || colorOf(brother.right) == BLACK)
        ) {
            colorRed(brother);
            fixAfterDeletion(parent);
        } else {
            useCase4(N);
        }
    }

    /**
     * case4:从当前的N视角看 brother == BLACK, N == BLACK, parent == RED(这也是从case3进入的case4视角看到的)
     * brother是case2中的brother的left
     * parent任然是case2中的parent
     *
     * 执行的手段是：如果brother双子黑且parent == RED, make brother == RED, parent == BLACK(这也是从case3进入的case4执行的手段)
     * 结果状态是，如果N(BLACK)是left, brother(RED)的(如果brother两孩子存在的话)left和right都是BLACK, parent(BLACK)的left是N,而且整棵树颜色平衡
     *
     * 如果brother有一个孩子是红色，那么进入case5
     * 结果状态是，如果N(BLACK)是left, brother(BLACK)的一个孩子是红色, parent(RED)的left是N
     * @param N
     */
    private void useCase4(BSTNode<K, V> N) {
        BSTNode<K, V> parent = N.parent;
        BSTNode<K, V> brother = getBrother(N, parent);
        if (
                colorOf(parent) == RED &&
                (brother.left == null || colorOf(brother.left) == BLACK) &&
                (brother.right == null || colorOf(brother.right) == BLACK)
        ) {
            colorRed(brother);
            colorBlack(parent);
        } else {
            useCase5(N);
        }
    }

    /**
     * case5:从当前的N视角看 oldBrother == BLACK, N == BLACK, parent == RED, brother的某个孩子是RED(这也是从case4进入的case5视角看到的)
     * oldBrother是case2中的brother的left
     * parent任然是case2中的parent
     *
     * 执行的手段是：
     *              如果oldBrother是right且oldBrother.left == RED
     *              如果oldBrother是left且oldBrother.right == RED     这两种情况构成了oldBrother内向的孩子是RED
     *              那么就make oldBrother == RED, oldBrother内向的RED孩子 = BLACK, 然后通过左旋或右旋实现“外向RED孩子”和“更新oldBrother”(这也是从case4进入的case5执行的手段)
     * 结果状态是，如果N(BLACK)是left, (如果oldBrother.left == RED，那么)新brother(BLACK) 是 oldBrother的left, parent(RED)的left是N, 且一定调用case6
     * @param N
     */
    private void useCase5(BSTNode<K, V> N) {
        BSTNode<K, V> parent = N.parent;
        BSTNode<K, V> oldBrother = getBrother(N, parent);
        if (N.isLeftChild && colorOf(oldBrother.right) == BLACK) {
            colorBlack(oldBrother.left);
            colorRed(oldBrother);
            rightRotate(oldBrother,oldBrother.left);
        } else if (!N.isLeftChild && colorOf(oldBrother.left) == BLACK) {
            colorBlack(oldBrother.right);
            colorRed(oldBrother);
            leftRotate(oldBrother, oldBrother.right);
        }
        useCase6(N);
    }

    /**
     * case6:从当前的N视角看 N == BLACK, brother == BLACK, parent == RED, brother的外向孩子是RED(这也是从case5进入的case6视角看到的)
     * brother是case5中的oldBrother的left或right
     * parent任然是case2中的parent
     *
     * 执行的手段是：
     *              如果brother是right且brother.right == RED
     *              如果brother是left且brother.left == RED     这两种情况构成了oldBrother外向的孩子是RED
     *              那么就make brother = parent的颜色, parent = BLACK, brother的外向RED孩子 == BLACK, 然后左旋或右旋"parent与brother"(这也是从case4进入的case5执行的手段)
     * 结果状态是，如果N(BLACK)是left, (如果brother.left存在，那么)新brother(BLACK) 是 brother的left, parent(BLACK)的left是N
     * @param N
     */
    private void useCase6(BSTNode<K, V> N) {
        BSTNode<K, V> parent = N.parent;
        BSTNode<K, V> brother = getBrother(N, parent);
        setBrotherColorFromParent(brother, colorOf(parent));//brother = parent的颜色
        colorBlack(parent);                                 //parent = BLACK
        if (N.isLeftChild) {
            colorBlack(brother.right);
            leftRotate(parent,brother);
        } else {
            colorBlack(brother.left);
            rightRotate(parent,brother);
        }
    }

    private void setBrotherColorFromParent(BSTNode<K, V> brother , boolean colorOfParent) {
        if (brother != null) {
            brother.isRed = colorOfParent;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        List<List<BSTNode<K, V>>> lists = super.levelOrder();
        for (List<BSTNode<K, V>> list : lists) {
            for (BSTNode<K, V> element : list) {
                sb.append(element.toString() + "\t");
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    public String toString2() {
        return super.toString();
    }
}
